题解 P4088 【[USACO18FEB]Slingshot】

发表于 | 更新于

题意:有一个数轴，上面有$n$ 个传送门，使用第$i$个传送门，你可以从$x_i$ 走到 $y_i$，花费的时间为 $t_i$ 秒。你的速度为$1 $格$/$秒，有 $m$ 次询问，每次你要从 $a_i$ 走到 $b_i$，最多使用一次传送门，问最少需要多少秒。

由于坐标很大，先离散化，然后离线处理询问，然后通过调整枚举顺序与在树状数组的插入位置等处理不同情况，手推一下应该不难理解，情况如下图所示

设$x,y$为弹弓左端点与右端点,$s,t$为查询左端点与右端点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int x,y,v,id;
}a[200200];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int c[200200],cnt,nm,px[200200],py[200200],ans[100100];
inline bool cmp(node a,node b){return (a.x!=b.x)?a.x<b.x:a.y<b.y;}
inline void change(int x,int d){
    for (;x<=cnt;x+=x&-x)
        c[x]=min(c[x],d);
}
inline int query(int x){
    int res=0x3f3f3f3f3f3f3f3f;
    for (;x;x-=x&-x)
        res=min(res,c[x]);
    return res;
}
signed main(){
    int n=read(),m=read();
    for (int i=1;i<=n;++i){
        int x=read(),y=read(),t=read();
        a[++cnt]=node{x,y,t,0};
        px[cnt]=x;py[cnt]=y;
    }
    for (int i=1;i<=m;++i){
        int x=read(),y=read();
        a[++cnt]=node{x,y,0,i};
        px[cnt]=x;py[cnt]=y;
        ans[i]=abs(y-x);
    }
    sort(px+1,px+1+cnt);
    sort(py+1,py+1+cnt);
    sort(a+1,a+1+cnt,cmp);
    nm=unique(px+1,px+1+cnt)-px-1;
    for (int i=1;i<=cnt;++i)a[i].x=lower_bound(px+1,px+1+nm,a[i].x)-px;
    nm=unique(py+1,py+1+cnt)-py-1;
    for (int i=1;i<=cnt;++i)a[i].y=lower_bound(py+1,py+1+nm,a[i].y)-py;//离散化
    memset(c,0x3f,sizeof(c));
    for (int i=1;i<=cnt;++i)
        if (!a[i].id)
            change(a[i].y,-px[a[i].x]-py[a[i].y]+a[i].v);
        else ans[a[i].id]=min(ans[a[i].id],query(a[i].y)+px[a[i].x]+py[a[i].y]);
    memset(c,0x3f,sizeof(c));
    for (int i=1;i<=cnt;++i)
        if (!a[i].id)
            change(cnt-a[i].y+1,-px[a[i].x]+py[a[i].y]+a[i].v);
        else ans[a[i].id]=min(ans[a[i].id],query(cnt-a[i].y+1)+px[a[i].x]-py[a[i].y]);
    memset(c,0x3f,sizeof(c));
    for (int i=cnt;i;--i)    
        if (!a[i].id)
            change(a[i].y,px[a[i].x]-py[a[i].y]+a[i].v);
        else ans[a[i].id]=min(ans[a[i].id],query(a[i].y)-px[a[i].x]+py[a[i].y]);
    memset(c,0x3f,sizeof(c));
    for (int i=cnt;i;--i)
        if (!a[i].id)
            change(cnt-a[i].y+1,px[a[i].x]+py[a[i].y]+a[i].v);
        else ans[a[i].id]=min(ans[a[i].id],query(cnt-a[i].y+1)-px[a[i].x]-py[a[i].y]);//四种情况
    for (int i=1;i<=m;++i)
        printf("%lld\n",ans[i]);
    return 0;
}